class MedianFinder {
public:
    MedianFinder() {}
    void addNum(int num) {
        // 第一次添加数或者添加的数小于大根堆的堆顶时
        if (maxheap.empty() || num < maxheap.top()) {
            maxheap.push(num);
            // 如果小根堆的size+1还小于大根堆的话就将大根堆的最大数插入到小根堆中
            // 这是因为插入了一个比大根堆顶还小的数导致中位数变小
            if (minheap.size() + 1 < maxheap.size()) {
                minheap.push(maxheap.top());
                maxheap.pop();
            }
        } else {
            minheap.push(num);
            // 如果小根堆的size大于大根堆的话就将小根堆的最小数插入到大根堆中
            // 这是因为插入了一个比小根堆顶还大的数导致中位数变大
            if (minheap.size() > maxheap.size()) {
                maxheap.push(minheap.top());
                minheap.pop();
            }
        }
    }

    double findMedian() {
        // 添加的数量为奇数时中位数为大根堆的堆顶
        if (maxheap.size() > minheap.size()) {
            return maxheap.top();
        }
        // 添加的数量为偶数时中位数为两个堆的堆顶数的平均值
        else {
            return (maxheap.top() + minheap.top()) / 2.0;
        }
    }

private:
    priority_queue<int, vector<int>, less<int>>
        maxheap; // 大根堆,中位数的左边,比中位数小
    priority_queue<int, vector<int>, greater<int>>
        minheap; // 小根堆，中位数的右边,比中位数大
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */